﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution827
{
    public int LargestIsland2(int[][] grid)
    {
        int m = grid.Length;
        int n = grid[0].Length;
        int res = MaxAreaOfIsland(grid);//不转换的最大面积
        Console.WriteLine(res);
        for (int i = 0; i < m; i++)
        {

            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 0)
                {
                    grid[i][j] = 1;
                  
                    int curCount = MaxAreaOfIsland(grid);
                    Console.WriteLine(curCount);
                    res = Math.Max(res, curCount);
                    Console.WriteLine(res);
                    grid[i][j] = 0;
                }

            }
        }
        return res;

    }
    public int MaxAreaOfIsland(int[][] grid)//计算最大岛的面积
    {
        int m = grid.Length;
        int n = grid[0].Length;
        int[][] grids = new int[m][];
        for (int i = 0; i < m; i++)
        {
            grids[i] = new int[n];
            Array.Copy(grid[i], grids[i], n);
        }

        bool[][] visted = new bool[m][];
        for (int i = 0; i < m; i++)
        {
            visted[i] = new bool[n];
        }
        int max = 0;
        for (int i = 0; i < m; i++)
        {

            for (int j = 0; j < n; j++)
            {


                if (grids[i][j] == 1)
                {
                    int count = DFS(grids, i, j, visted);
                    max = Math.Max(max, count);


                }


            }


        }
        return max;
    }
    int DFS(int[][] grids, int i, int j, bool[][] visted)
    {
        int m = grids.Length;
        int n = grids[0].Length;



        visted[i][j] = true;
        grids[i][j] = 0;
        int left = 0;
        int right = 0;
        int top = 0;
        int bot = 0;

        if (i - 1 >= 0 && grids[i - 1][j] == 1)
        {



            top = DFS(grids, i - 1, j, visted);


        }

        if (i + 1 < m && grids[i + 1][j] == 1)
        {



            bot = DFS(grids, i + 1, j, visted);
        }

        if (j + 1 < n && grids[i][j + 1] == 1)
        {



            right = DFS(grids, i, j + 1, visted);
        }

        if (j - 1 >= 0 && grids[i][j - 1] == 1)
        {



            left = DFS(grids, i, j - 1, visted);

        }


        return left + right + top + bot + 1;
    }




}


class Sol827
{

    //使用一个tag，既可以标记点是否遍历过(防止改变数组）。又可以判断点属于哪个数组
    public int LargestIsland(int[][] grid)
    {
        int n = grid.Length;
       
        int res = 0;

        int[][] tags = new int[n][];
        for (int i = 0; i < n; i++)
        { tags[i] = new int[n]; }

        Dictionary<int,int> map = new Dictionary<int,int>();

        for (int i = 0; i < n; i++)//先记录每个岛屿的归属和大小
        {

            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1&& tags[i][j]==0)
                {
                   int tag = i * n + j+1;
                   int curCount= DFS(grid, i, j, tag, tags);
                    map[tag] = curCount;
                    
                    res =Math.Max(res, curCount);


                  
                }

            }
        }

        for (int i = 0; i < n; i++)
        {

            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 0)
                {
                    int newCount = 1;
                    HashSet<int> set = new HashSet<int>();  
                    

                    //检查周围的岛，而且不能是一个岛
                    if (i - 1 >= 0 && !set.Contains(tags[i - 1][j]) && tags[i - 1][j] != 0)
                    {



                        newCount += map[tags[i - 1][j]];//加上旁边的面积
                        Console.WriteLine(newCount);
                        set.Add(tags[i - 1][j]);

                    }

                    if (i + 1 < n && !set.Contains(tags[i + 1][j]) && tags[i + 1][j] != 0)
                    {



                        newCount += map[tags[ i + 1][j]];//加上旁边的面积
                        Console.WriteLine(newCount);
                        set.Add(tags[ i + 1][j]);
                    }

                    if (j + 1 < n && !set.Contains(tags[i ][j + 1]) && tags[i][j + 1] != 0)
                    {



                        newCount += map[tags[i ][j + 1]];//加上旁边的面积
                        Console.WriteLine(newCount);
                        set.Add(tags[i ][j + 1]);
                    }

                    if (j - 1 >= 0 && !set.Contains(tags[i][j - 1])  && tags[i][j - 1] != 0)
                    {



                        newCount += map[tags[i][j - 1]];//加上旁边的面积
                        Console.WriteLine(newCount);
                        set.Add(tags[i][j - 1]);

                    }
                    
                  res=Math.Max(res, newCount);
                    Console.WriteLine(newCount);
                }

            }
        }
        return res;

    }

    int DFS(int[][] grids, int i, int j, int tag, int[][] tags)
    {
        int n = grids.Length;
    
        tags[i][j] = tag;
        int left = 0;
        int right = 0;
        int top = 0;
        int bot = 0;

        if (i - 1 >= 0 && grids[i - 1][j] == 1&& tags[i - 1][j] ==0)
        {



            top = DFS(grids, i - 1, j, tag, tags);


        }

        if (i + 1 < n && grids[i + 1][j] == 1 && tags[i + 1][j] == 0)
        {



            bot = DFS(grids, i + 1, j, tag, tags);
        }

        if (j + 1 < n && grids[i][j + 1] == 1 && tags[i][j + 1] == 0)
        {



            right = DFS(grids, i, j + 1, tag, tags);
        }

        if (j - 1 >= 0 && grids[i][j - 1] == 1 && tags[i][j - 1] == 0)
        {



            left = DFS(grids, i, j - 1, tag, tags);

        }


        return left + right + top + bot + 1;
    }
}

class Program827
{


    static void Main827(string[] args)
    {

        Sol827 solution = new ();
        int[][] grid = [[1, 0], [0, 1]];
        int res = solution.LargestIsland(grid);
        Console.WriteLine(res);
    }
}